package developer.算法.动态规划.完全平方数;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author zhangyongkang
 * @time 2025/4/8 16:07
 * @description 279. 完全平方数
 * 中等
 * 相关标签
 * 相关企业
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 * <p>
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，
 * 其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 * 示例 2：
 * <p>
 * 输入：n = 13
 * 输出：2
 * 解释：13 = 4 + 9
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 104
 */
public class WanquanPingFangShu {
    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        System.out.println(solution.numSquares(12));
        System.out.println(solution.numSquares(13));
    }

    static class Solution4 {
        public int numSquares(int n) {
            int[] dp = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++) {
                    min = Math.min(min, dp[i - j * j]);
                }
                dp[i] = min + 1;
            }
            return dp[n];
        }
    }


    static class SolutionSelf3 {
        public int numSquares(int n) {
            int[] dp = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++) {
                    min = Math.min(min, dp[i - j * j]);
                }
                dp[i] = min + 1;
            }
            return dp[n];
        }

    }

    static class SolutionSelf {

        public int numSquares(int n) {
            int[] dp = new int[n + 1];

            for (int i = 1; i <= n; i++) {
                //dpi
                int min = Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++) {
                    min = Math.min(min, dp[i - j * j]);
                }
                dp[i] = min + 1;
            }
            return dp[n];
        }
    }

    //回溯的思想。。  但是leetcode 超时
    static class Solution {
        List<List<Integer>> result;
        boolean hasVal;

        public int numSquares(int n) {
            result = new ArrayList<>();
            hasVal = false;
            List<Integer> minSqrts = new ArrayList<Integer>();
            for (int i = 1; ; i++) {
                int val = i * i;
                if (val <= n) {
                    minSqrts.add(val);
                } else {
                    break;
                }
            }
            Collections.reverse(minSqrts);
            //进行回溯
            dfs(0, new ArrayList<>(), n, minSqrts, 0, minSqrts.size());
            return result.stream()
                    .min((a, b) -> a.size() - b.size())
                    .get()
                    .size();
        }

        private void dfs(int currentVal, List<Integer> current, int target, List<Integer> datas, int start, int end) {
            if (currentVal == target) {
                hasVal = true;
                result.add(new ArrayList<>(current));
                return;
            }
            if (currentVal > target) {
                return;
            }
            for (int i = start; i < end; i++) {
                currentVal += datas.get(i);
                current.add(datas.get(i));
                if (hasVal) {
                    break;
                }
                dfs(currentVal, current, target, datas, i, end);
                currentVal -= datas.get(i);
                current.remove(current.size() - 1);
            }
        }
    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/perfect-squares/solutions/822940/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * <p>
     * 我们可以依据题目的要求写出状态表达式：f[i] 表示最少需要多少个数的平方来表示整数 i。
     * <p>
     * 这些数必然落在区间 [1,
     * i
     * ​
     * ]。我们可以枚举这些数，假设当前枚举到 j，那么我们还需要取若干数的平方，构成 i−j
     * 2
     * 。此时我们发现该子问题和原问题类似，只是规模变小了。这符合了动态规划的要求，于是我们可以写出状态转移方程。
     * <p>
     * f[i]=1+
     * j=1
     * min
     * ⌊
     * i
     * ​
     * ⌋
     * ​
     * f[i−j
     * 2
     * ]
     * 其中 f[0]=0 为边界条件，实际上我们无法表示数字 0，只是为了保证状态转移过程中遇到 j 恰为
     * i
     * ​
     * 的情况合法。
     * <p>
     * 同时因为计算 f[i] 时所需要用到的状态仅有 f[i−j
     * 2
     * ]，必然小于 i，因此我们只需要从小到大地枚举 i 来计算 f[i] 即可。
     * <p>
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/perfect-squares/solutions/822940/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class SolutionOfficial {
        public int numSquares(int n) {
            int[] f = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                int minn = Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++) {
                    minn = Math.min(minn, f[i - j * j]);
                }
                f[i] = minn + 1;
            }
            return f[n];
        }
    }


}
